package leetcode.median;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

import leetcode.base.TreeNode;

public class $508_FindFrequentTreeSum {

    int maxTime = 0;

    public int[] findFrequentTreeSum(TreeNode root) {
        Map<Integer, Integer> map = new HashMap<>();

        dfs(root, map);
        return map.entrySet().parallelStream().filter(entry -> entry.getValue() == maxTime).mapToInt(Map.Entry::getKey).toArray();
    }

    public int dfs(TreeNode root, Map<Integer, Integer> map) {
        if (root == null) {
            return 0;
        }

        int leftSum = dfs(root.left, map);
        int rightSum = dfs(root.right, map);
        int curSum = leftSum + rightSum + root.val;

        map.put(curSum, map.getOrDefault(curSum, 0) + 1);
        maxTime = Math.max(maxTime, map.get(curSum));
        return curSum;
    }


}
